package main

import (
	"fmt"
	"os"
)

func readMaze(fileName string)  [][]int{

	file, e := os.Open(fileName)
	if e != nil {
		panic("file read error")
	}

	var row, column int
	//读取文件第一行的前两列,并将读到的值放入row和column中
	fmt.Fscanf(file, "%d %d", &row, &column)

	//定义了maze[]的长度，maze[]中的元素类型是[]int
	maze := make([][]int, row)
	for rowIdx, _ := range maze{
		//赋值，上面只是定义
		maze[rowIdx] = make([]int, column)
		for colIdx, _ := range maze[rowIdx] {
			//赋值，需要&maze接收
			fmt.Fscanf(file, "%d",&maze[rowIdx][colIdx])
		}
	}

	return maze
}

type point struct {
	i,j int
}
var directionalPoints = []point {
	//按上左下右原则:
	{-1,0},{0,-1},{1,0},{0,1},
}

func (p point) add(r point) point{
	return point{p.i+r.i,p.j+r.j}
}

func (p point) at(maze [][]int) (int, bool) {
	//p.i < 0 初始时只计算第二象限的数据
	if p.i < 0 || p.i >= len(maze){
		return 0, false
	}
	if (p.j <0 || p.j >= len(maze[p.i])){
		return 0, false
	}

	return maze[p.i][p.j],true

}

func walk(maze [][]int, startNode point, endNode point) [][]int{
	var pointQueue []point
	//构造一个和maze一样的数组，用来存放运动轨迹，初始时0
	track :=  make([][]int, len(maze))
	for idx,_ := range track {
		track[idx] = make([]int, len(maze[idx]))
	}

	pointQueue = append(pointQueue, startNode)
	for len(pointQueue) >0 {
		curNode := pointQueue[0]
		pointQueue = pointQueue[1:]
		if curNode == endNode{
			break
		}
		for _,directionalPoint := range directionalPoints{
			//下个节点的坐标
			nextNode := curNode.add(directionalPoint)

			//step1 节点的位置不越界并且为0
			mazeNodeVal, ok := nextNode.at(maze)
			if !ok || mazeNodeVal ==1 {
				continue
			}
			//step2 节点在轨迹track中是一个新的位置（==0）
			nextNodeVal, ok := nextNode.at(track)
			if !ok || nextNodeVal !=0 {
				continue
			}
			//step3 节点不等于开始节点
			if nextNode == startNode{
				continue
			}

			//跟新轨迹坐标(track)中的元素
			curNodeVal, _ := curNode.at(track)
			track[nextNode.i][nextNode.j] = curNodeVal+1

			//追加节点
			pointQueue = append(pointQueue, nextNode)
		}

	}
	return track
}

func main() {
	maze := readMaze("maze/maze.in")
	result := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})

	for _,row := range result{
		for _, cell := range row {
			fmt.Printf("%3d", cell)
		}
		fmt.Println()
	}
}
